(구)정보과학회 논문지
Current Result Document :
| 한글제목(Korean Title) |
네트워크상의 강결합 요소를 구하는 최적의 분산 알고리즘 |
| 영문제목(English Title) |
An Optimal Distributed Algorithm for Finding Strongly Connected Components |
| 저자(Author) |
조이남
박정호
Leenam Cho
Jungho Park
|
| 원문수록처(Citation) |
VOL 19 NO. 04 PP. 0409 ~ 0420 (1992. 07) |
한글내용
(Korean Abstract) |
어떤 문제를 해결하기 위한 정보가 네트워크상의 프로세서에게 분산되어 있는 상황에서 그들 정보를 교환하면서 그 문제를 해결하는 알고리즘을 분산 알고리즘이라고 한다. 본 논문에서는 비동기식 네트워크에서 강결합 요소를 구하는 문제를 해결하는 최적의 분산 알고리즘을 제안한다. 일반적으로 분산 알고리즘의 효율은 실행중에 교환되는 메세지의 총수(메세지 복잡도)와 통신지연을 1 단위시간으로 했을 때의 실행시간(이상시간 복잡도)으로 평가된다. 본 논문에서 제안하는 분산 알고리즘의 메세지 복잡도는 O(e), 이상시간 복잡도는 O(n)이다. 여기서, e는 네트워크 상의 링크수, n은 프로세서수를 나타낸다. 그리고, 본 논문에서는 강결합 요소를 구하는 문제의 메세지 복잡도의 하계가 Ω(e), 이상시간 복잡도의 하계가 Ω(n)이라는 것을 증명한다. 따라서, 본 논문에서 제안하는 알고리즘은 메세지의 이상시간 복잡도에 관해서 최적(optimal)이다.
|
영문내용
(English Abstract) |
Consider the situation that information necessary to solve a certain problem are distributed among processors on a network. It is called a distributed algorithm that in this situation each processor exchanges the message with adjacent processors to solve the problem. In this paper, we propose an optimal distributed algorithm to solve the problem that finds the strongly connected components in an asynchronous network system. In general, a distributed algorithm is estimated by the number of messages(messages complexity) and the number of unit complexity(ideal-time complexity). Message complexity and ideal-time complexity of the distributed algorithm proposed in this paper are O(e) and O(n) respectively, where n is the number of processors on the network, and e is the number of links. And this paper proves that the lower bound of message complexity of the strongly connected component problem is Ω(e) and that the lower bound of ideal-time complexity of the problem is Ω(n). Therefore, our algorithm proposed in this paper is optimal with respect to these complexities.
|
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
